At present, non-volatile memory has been widely used in computers, communications and consumer electronics products. For example, U disk, MP3, digital cameras, mobile communications terminal, solid-state hard disk and other products use the non-volatile memory as the storage medium. As these products continue to increase storage capacity requirements and process geometries of the non-volatile memory continue to shrink, the reliability of non-volatile memory is facing more and more severe challenges. Especially, the erase number of the minimum unit physical block of erase operation of the nonvolatile memory is limited; this will cause serious influence on the service life of the nonvolatile memory. For the problem that the erase number of the physical block is limited, the existing technology requires wear leveling operations to be performed on the physical block. Via controlling the erase operations of the physical block, it tries to distribute erase operations evenly over all physical blocks of the memory to avoid that some physical blocks experience higher numbers of erase operation and reach the upper limit of the erase number sooner than other physical blocks and fail, which causes the memory as a whole failed in the condition that most physical blocks are still far from their end of life.
The wear leveling includes two kinds, i.e., dynamic wear leveling which dynamically balances the erase numbers of all physical block by controlling the written physical blocks in data writing process, and static wear leveling which statically balances the erase numbers of all physical block by adjusting the distribution of the cold and hot data (the data which is frequently erased is called hot data, and the data which is not frequently erased is called cold data) stored in the physical blocks. For these two kinds of wear leveling, the existing technology has brought forward many algorithms, but these algorithms have not well solved the contradiction between wear leveling effect and reduction of the additional wear caused by the wear leveling algorithms themselves. Further, the implementation of the existing wear leveling algorithms is based on saving wear information of each physical block; with the increased memory capacity, the number of the physical blocks in the memory which the wear leveling is required to be performed on is greatly increased. When the wear leveling algorithm is implemented, the speed of searching for wear information of the physical blocks also becomes slower and slower.
A widely used representative wear leveling algorithm “Dual-Pool algorithm” will be taken as an example in the following to elaborate on the existing technology.
As shown in FIG. 1, this algorithm is an integrated algorithm which combines dynamic wear leveling and static wear leveling. This algorithm sets cool pool and hot pool properties for physical blocks, and defines EC as a total erase number of the physical block, EEC as a restarted cumulative erase number (hereinafter referred to as the effective erase number) of the physical block after changes of hot and cool pool properties of the physical blocks, PT as marks of the hot and cool pools properties of the physical block, in which CP represents cool pool, and HP represents hot pool. Wear information for each physical block needed to be recorded includes EC, EEC and PT.
In this algorithm, QCPEC, QHPEC, QCPEEC, QHPEEC are respectively defined as a queue of the erase numbers of the cool pool, a queue of the erase numbers of the hot pool, a queue of the effective erase numbers of the cool pool, and a queue of the effective erase numbers of the hot pool. H+(Q) and H−(Q) are respectively defined as functions of the maximum and minimum values (specific physical block) returned to the queue Q. EC(B) is a function of the total erase number returned to the physical block B. EEC(B) is a function of the effective erase number returned to the physical block B.
The specific implementation process of this algorithm is shown in FIG. 1 and includes the following steps:
Step 101: obtaining wear information; before implementing the Dual-Pool algorithm, it is needed to first obtain wear information of all the physical blocks and then manage the physical blocks. The step of obtaining wear information is usually completed in the power-up initialization process of the memory which can be divided into two situations: if the memory is non-first used, the wear information can be recorded in the memory (such as backup area which is specifically carved out of the memory, invisible to the user and used to store management information) when the memory was normally uninstalled, during the power-up initialization process of the memory, it is only needed to read the data of the backup area of the memory to obtain the wear information; if the memory is first used, no data is in the backup area, at this moment, it is needed to build wear information, i.e., setting EC and EEC to be 0, marking cold and hot pool properties for the physical blocks, and dividing the physical blocks into cool pool or hot pool; the specific method for dividing the physical blocks into cool pool or hot pool can be arbitrary, such as random division.
Step 102: determining whether there is a written request, if yes, proceeding to step 103, otherwise proceeding to step 117;
Step 103: determining whether written block allocated to write the request has been filled, if yes, proceeding to step 104, otherwise proceeding to step 105;
Step 104: allocating blank block to write the request from the pre-set blank block queue according to the new allocation to the new (FIFO) approach (according to orders of entering into the blank block queue, the blank block first entering into the queue will be first allocated), proceeding into step 105;
Step 105: responding to the written request and writing data to the allocated written block;
Step 106: determining whether the difference between EC(H+(QHPEC)) and EC(H−(QCPEC)) exceeds the set threshold TH, if yes, proceeding to step 107, otherwise, proceeding to step 111;
Step 107: compulsively recycling the H+(QHPEC) physical block, i.e., copying valid data stored in this physical block to other physical block and erasing the data stored in the H+(QHPEC) physical block;
Step 108: copying data of the H−(QCPEC) physical block to the H+(QHPEC) physical block;
Step 109: erasing the data of the H−(QCPEC) physical block so that the H−(QCPEC) physical block becomes a blank block;
Step 110: exchanging the cool and hot cool properties of the H−(QCPEC) and H+(QCPEC) due to the changes of the cool and hot cool properties, EEC of each of the H−(QCPEC) and H+(QHPEC) physical blocks will be cleared and restart to accumulate;
Step 111: determining whether the difference between EC(H+(QHPEC)) and EC(H−(QCPEC)) exceeds two times of the threshold TH, if yes, proceeding to step 112, otherwise, proceeding to step 113;
Step 112: adjusting PT of the H−(QHPEC) physical block from hot pool to cool pool;
Step 113: determining whether the difference between EEC(H+(QCPEEC)) and EEC(H−(QHPEEC)) exceeds the threshold TH, if yes, proceeding to step 114, otherwise, proceeding to step 115;
Step 114: adjusting PT of the H+QCPEEC physical block from cool pool to hot pool;
Step 115: determining whether available space of the memory is less than pre-set threshold, if yes, proceeding to step 116, otherwise returning back to step 102;
Step 116: recycling garbage, returning back to step 102;
Step 117: determining whether the memory is uninstalled, if yes, proceeding to step 118, otherwise returning back to step 102;
Step 118: saving the wear information, and ending the process.
In the above steps, steps 102˜103, 105 are the normal process of writing data, step 104 is the dynamic wear leveling part of this algorithm, i.e., controlling the allocation of the blank blocks through the blank block queue adopting the FIFO mode to achieve the effect of dynamic wear-leveling.
Steps 106˜114 are static wear leveling part of this algorithm, which moves the cool and hot data stored in the H+(QHPEC) and H−(QCPEC), and exchanges the cool and hot properties of the H+(QHPEC) and the H−(QCPEC), so that physical blocks of high erase numbers store the cool data and enter into the cool pool to slow wear, physical blocks of small erase numbers store the hot data and enter into the hot pool to accelerate wear, thereby achieving the purpose of wear leveling.
Step 115 is followed by the process of recycling garbage and uninstalling of the memory; the recycling garbage includes the process of data transferring and erasing. The so-called data transferring means that data marked as valid must be copied to other blocks before being erased; the so-called erasing process means a process that the physical block to which date have been written and of which all data has been marked as invalid, i.e., garbage block, is erased to obtain a blank block. The existing garbage recycling process generally randomly selects garbage block, and the dynamic leveling part of the Dual-Pool algorithm does not improve the process of recycling garbage. Further, in the uninstall process, the memory can store the wear information (such as EC, EEC, PT and blank block queue), which is needed by the Dual-Pool algorithm to prepare for use in the next booing of the memory.
Obviously, in order to statically level the erase numbers of all the physical blocks, the Dual-Pool algorithm needs to move the valid data of the two physical blocks H+(QHPEC) and H−(QCPEC), and erase the two physical blocks H+(QHPEC) and H−(QCPEC). This will have a greater system overhead and additionally increase the erase numbers of the physical blocks, i.e., additional wear; this is a counter-effect for the purpose of wear leveling, i.e. this is a counter-effect for the purpose of increasing the lifetime of the memory.
Further, since the Dual-Pool algorithm needs to calculate EC(H+(QHPEC)) and EC(H−(QCPEC)), this requires traversing all the physical blocks of the entire memory before running further. However, as storage capacity continues to increase, the number of the physical blocks is also increasing, the speed of searching for the physical blocks also becomes slower and slower.